import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/18 20:40
 * @description 从后往前遍历
 */
public class Solution {
    public static void main(String[] args) {

    }

    Map<String, Integer> map = new HashMap<>();

    public String countOfAtoms(String formula) {
        int L = formula.length();
        int num = 1;
        // 保存倍数
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1);
        // 从后往前
        for (int i = L - 1; i >= 0; i--) {
            char c = formula.charAt(i);
            if (c >= 'A' && c <= 'Z') {
                map.put(String.valueOf(c), (stack.peek() * num) + map.getOrDefault(String.valueOf(c), 0));
                num = 1;
            } else if (c >= 'a' && c <= 'z') {
                // 出现形如 Mg 这样的原子
                int j = i;
                StringBuilder temp = new StringBuilder();
                char ch = formula.charAt(j);
                while (ch >= 'a' && ch <= 'z') {
                    temp.insert(0, ch);
                    j--;
                    ch = formula.charAt(j);
                }
                temp.insert(0, ch);
                map.put(temp.toString(), (stack.peek() * num) + map.getOrDefault(temp.toString(), 0));
                num = 1;
                i = j;
            } else if (Character.isDigit(c)) {
                num = 0;
                int j = 0;
                char ch = formula.charAt(i - j);
                while (Character.isDigit(ch)) {
                    num = (ch - '0') * (int) Math.pow(10, j) + num;
                    j++;
                    ch = formula.charAt(i - j);
                }
                i = i - j + 1;
            } else if (c == ')') {
                stack.push(num * stack.peek());
                num = 1;
            } else if (c == '(') {
                stack.pop();
            }
        }
        StringBuilder str = new StringBuilder();
        Object[] names = map.keySet().toArray();
        Arrays.sort(names);
        for (Object s : names) {
            str.append(s);
            if (map.get((String) s) != 1) {
                str.append(map.get((String) s));
            }
        }
        return str.toString();
    }
}
